package cuiyt.algorithm.union.optimization;

import algorithm.union.UnionQu;

import java.lang.annotation.ElementType;

/**
 * @author cyt
 * @create 2020-09-05 16:20
 */
public class UnionQuRank extends UnionQu {
    private int[] rank;

    public UnionQuRank(int cap) {
        super(cap);
        rank = new int[cap];
        for (int i = 0; i < cap; i++) {
            rank[i] = 1;
        }
    }

    /**
     * 基于 节点之间 高度的优化
     *
     * @param a
     * @param b
     */
    @Override
    public void union(int a, int b) {
        int value_A = find(a);
        int value_B = find(b);
        if (value_A == value_B) {
            return;
        }
        if (rank[value_A] > rank[value_B]) {
            parents[value_B] = value_A;
        } else if (value_A < value_B) {
            parents[value_A] = value_B;
        } else {
            parents[value_A] = value_B;
            rank[value_B] += 1;
        }

    }
}
